// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-10 22:31
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.TREE;

import com.DataStruct.Tree.TwoBinaryTree.TreeNode;

import java.util.*;

@SuppressWarnings("ALL")
public class LevelOrder {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        lO(root, ans);
        return ans;
    }

    private void lO(TreeNode root, List<List<Integer>> ans) {
        if (root == null) {
            return;
        }
        int cnt = 0;
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
        int layer = 1, nlayer = 0;
        while (!deque.isEmpty()) {
            TreeNode node = deque.pollFirst();
            layer--;
            res.add(node.val);
            if (node.left != null) {
                deque.addLast(node.left);
                nlayer++;
            }
            if (node.right != null) {
                deque.addLast(node.right);
                nlayer++;
            }
            if (layer == 0) {
                layer = nlayer;
                nlayer = 0;
                if (cnt % 2 == 1) {
                    res = reverse(res);
                }
                ans.add(new ArrayList<>(res));
                res.clear();
                cnt++;
            }
        }
    }

    private List<Integer> reverse(List<Integer> res) {
        List<Integer> ans = new ArrayList<>();
        for (int i = res.size() - 1; i >= 0; i--) {
            ans.add(res.get(i));
        }
        return ans;
    }
}
